﻿using leetcodeAnswer.Code;
using System;
using System.Collections.Generic;
using System.Text;

namespace leetcodeAnswer.Answer
{
    [Answer(
        Index = 3,
        Name = "无重复字符的最长子串",
        Url = "https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/",
        Descript = @"给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: ""abcabcbb""
输出: 3
解释: 因为无重复字符的最长子串是 ""abc""，所以其长度为 3。
示例 2:

输入: ""bbbbb""
输出: 1
解释: 因为无重复字符的最长子串是 ""b""，所以其长度为 1。
示例 3:

输入: ""pwwkew""
输出: 3
解释: 因为无重复字符的最长子串是""wke""，所以其长度为 3。

    请注意，你的答案必须是 子串 的长度，""pwke""是一个子序列，不是子串。")]
    public class No_003_LengthOfLongestSubstring
    {
        [AnswerRun]
        public int LengthOfLongestSubstring(String s)
        {
            int[] isValid = new int[95];
            int result = 0;
            int max = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (isValid[s[i] - ' '] != 0)
                {
                    result = max > result ? max : result;
                    for (int j = i - max; j < isValid[s[i] - ' ']; j++)
                    {
                        max--;
                        isValid[s[j] - ' '] = 0;
                    }
                }
                max++;
                isValid[s[i] - ' '] = i + 1;
            }
            return max > result ? max : result;
        }

        /// <summary>
        /// 验证参数
        /// </summary>
        [AnswerParameter]
        public List<object[]> Parameter { get; set; }

        public No_003_LengthOfLongestSubstring() {
            Parameter = new List<object[]>() {
                new object[]{ "abcabcbb" },
                new object[]{ "bbbbb" },
                new object[]{ "pwwkew" },
                new object[]{ " " },
                new object[]{ "" },
                new object[]{ "dvdf" }
            };
        }
    }
}
